import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Date;
import java.util.LinkedList;


public class Retrace {
	
	public int[][] rankArray;
	Board board,swapedBoard;
	public int rows,cols;
	PlayerNBoxesReverse startPNB,swapedPNB;
	Position[] goals;
	Position[] boxes;
	Position player;
	long cnt = 0;
	long start = 0;
	boolean isFinished = false;
	Move fm;
	
	LinkedList<PlayerNBoxesReverse> visitedStates = new LinkedList<PlayerNBoxesReverse>();
	
	public ArrayList<Move> retraceInterface() throws CloneNotSupportedException
	{
		return solve(swapedPNB);
	}
	public ArrayList<Move> solve(PlayerNBoxesReverse pnb) throws CloneNotSupportedException{
		visitedStates.add(pnb);
		return solveHelper(pnb);
	}
	public ArrayList<Move> solveHelper(PlayerNBoxesReverse swapedPNB) throws CloneNotSupportedException{
//		depth ++;
//		if ( depth > 300 ){
//			System.out.println("max Depthhttps://www.facebook.com/ Reached!");
//			return new  ArrayList<Move>();
//		}
		
		cnt++;
		if ( cnt % 1000 == 0){
			long end= ((new  Date().getTime())-start);
			//System.out.println(cnt+". solve....... visitedStates.size: "+visitedStates.size()+ " time: "+end+"ms = "+end/1000+"s = "+end/1000/60.+"min = "+end/1000/60/60.0+"h");
		}
//		for ( PlayerNBoxesReverse i : visitedStates){
//			System.out.print(i+" | ");
//		}
//		System.out.println("");
		
		byte[][] jointedBoard = Helper.joinBoards(swapedBoard, swapedPNB);
		//System.out.println("Justed joined a board ");
		//System.out.println(Board.toString(jointedBoard, jointedBoard.length, jointedBoard[0].length));
		
		
		if ( swapedBoard.isFinished(swapedPNB)){
			
//			System.out.println("Solution Found"+swapedPNB.toString());
			isFinished = true;
		    ArrayList<Move> finalMove=new ArrayList<Move>();
		    //finalMove.add(fm);
		    return finalMove;
		}
		
		ArrayList<Move> re = new ArrayList<Move>();
		ArrayList<Move> possibleMoves = Assist.possibleMoveBox(swapedBoard, swapedPNB);
		
		ArrayList<Move> unvisitedStates =  new ArrayList<Move>();
		PlayerNBoxesReverse nextState;
//        System.out.println("possible Moves: ");
//        for ( Move pos : possibleMoves){
//        	System.out.println(pos);
//        }
		int c=0;
		for ( Move m: possibleMoves){
			// do a move
			nextState = Assist.boxMove(swapedPNB, m);
			if ( Assist.isItADeadlock(swapedBoard, nextState)){
				continue;
			}
			//c++;
			//System.out.println(m.getDirection()+ "for the box at"+ c +m.getStart().toString());
			
			// if it is not a visited state
			int index = Collections.binarySearch(visitedStates, nextState);
			//System.out.println("error test");
			if( index < 0){
				visitedStates.add(-index-1, nextState);
				unvisitedStates.add(m);
				//System.out.println("now visiting: "+visitedStates.get(-index-1));
			}else{
				//System.out.println("already visited: "+visitedStates.get(index));
			}
		}
		// sort all unvisited moves by ranking
		// sort by ranks
		ArrayList<Move> ranked = new ArrayList<Move>();
		ranked = Helper.rankListOfMove(unvisitedStates, rankArray, swapedPNB, swapedBoard);
		
		for ( Move m: ranked){
			

			nextState = Assist.boxMove(swapedPNB, m);
			
			
			re.addAll(solveHelper(nextState));
			
//			depth --;
			if ( isFinished){
				//System.out.println(m.getDirection()+ "adding the "+ c +m.getStart().toString());
				
				re.add(m);
				return re;
			}
		}
//		System.out.println("backtracking... to : "+pnb);
		
		return re;
	}	
	
	public void addInOrder(PlayerNBoxesReverse n){
		visitedStates.add(Collections.binarySearch(visitedStates,n) , n);
	}
	
	
	public Retrace(Board board,PlayerNBoxesReverse pnb)
	{
		this.board = board;
		
		rows=board.getNumRows();
        cols=board.getNumColumns();
        
        
        startPNB=pnb;
        ArrayList<Position> Goals;
        Goals=BoardRanker.findGoals(board);
        
        setGoals(Goals);
        boxes=startPNB.getBoxes();
        player=startPNB.getPlayer();
        
        
        //swapedPNB.setBoxes(Goals);
        //swapedPNB=new PlayerNBoxesReverse(boxes[0],Goals);
        swapedPNB=new PlayerNBoxesReverse(player,Goals);
        swaper(board,pnb);
        
        rankArray = BoardRanker.distancesToAllTarget(swapedBoard);
		
		//System.out.println(board);
		//System.out.println(startPNB.toString());
		////System.out.println(Assist.arrayToString(rankArray));
		
		
		
		
	}
	
	public void swaper(Board board,PlayerNBoxesReverse pnb)
	{
		swapedBoard=new Board(rows,cols);
		
		
		for(int i=0;i<rows;i++)
			for(int j=0;j<cols;j++)
			{
				if(board.getData(i, j)==Board.WALL)
					swapedBoard.setData(i,j,Board.WALL);
				else
					swapedBoard.setData(i,j,Board.EMPTY);
			}
		for ( Position pos : boxes){
			swapedBoard.setData(pos,Board.GOAL);
			
		}
		
		//System.out.println(swapedBoard);
		
		
	}
	
	public void setGoals(ArrayList<Position> Goals){
		goals = new Position[Goals.size()];
		for ( int i = 0; i < Goals.size(); i++){
			goals[i] = Goals.get(i);
		}
		java.util.Arrays.sort( goals);
	}

	
	

}
